package mystack;

import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }

    public void push(int val) {
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    public int pop() {
        int oldVal = 0;
        try {
            oldVal = elem[usedSize - 1];
        } catch (StackIsEmptyExcepyion e) {
            e.printStackTrace();
        }
        //进行删除，若是引用类型需要置为null
        usedSize--;
        return oldVal;
    }

    public void empty() {
        if (usedSize == 0) {
            throw new StackIsEmptyExcepyion("栈为空");
        }
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            //定义一个tmp用来接收数组的值
            String tmp = tokens[i];
            //如果传入的是符号，则出栈两个元素，进行运算，然后再将结果压入栈中
            if (tmp.equals("+") || tmp.equals("-") || tmp.equals("*") || tmp.equals("/")) {
                int val1 = stack.pop();
                int val2 = stack.pop();
                switch (tmp) {
                    case "+":
                        stack.push(val2 + val1);
                        break;
                    case "-":
                        stack.push(val2 - val1);
                        break;
                    case "*":
                        stack.push(val2 * val1);
                        break;
                    case "/":
                        stack.push(val2 / val1);
                        break;
                }
            }else {
                //如果传入的不是符号，将字符串tmp转化为Integer类型的数据，再压入栈中
                Integer val = Integer.valueOf(tmp);
                stack.push(val);
            }
        }
        //最终，返回栈中的最后一个元素，这就是计算出的结果
        return stack.pop();
    }

    public boolean isValid(String s) {
        //创建一个放字符的栈
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //拿到一个字符
            char ch = s.charAt(i);
            //1. 左括号入栈
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else {
                //2. 遇到右括号
                if(stack.empty())
                    //如果是空的话就没有左括号和其匹配
                    return false;
                else{
                    //取栈顶的元素，看和当前右括号是否匹配
                    char chL = stack.peek();
                    if(chL == '(' && ch == ')' || chL == '[' && ch == '}' || chL == '{' && ch == '}'){
                        //4. 证明当前这对括号是匹配的
                        stack.pop();
                    }else {
                        //5. 当前括号不匹配
                        return false;
                    }
                }
            }
        }
        return stack.empty();
    }


    public boolean IsPopOrder (int[] pushV, int[] popV) {
        //需要一个栈，将pushV里面的元素放进去
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            //依次入栈
            stack.push(pushV[i]);

            //看栈顶元素和 j下标的元素是否一样
            //前提是栈不为空，j不越界
            while(!stack.empty() && j < popV.length && stack.peek() == popV[j]){
                //若一样，则出栈
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

    class MinStack {
        Stack<Integer> stack;
        Stack<Integer> minStack;

        public MinStack() {
            stack = new Stack<>();
            minStack = new Stack<>();
        }

        public void push(int val) {
            stack.push(val);
            if(minStack.empty()){
                minStack.push(val);
            }else {
                Integer peekVal = minStack.peek();
                if(val <= peekVal){
                    minStack.push(val);
                }
            }
        }

        public void pop() {
            if(stack.empty()){
                return;
            }
            int popVal = stack.pop();
            if(popVal == minStack.peek()){
                minStack.pop();
            }
        }

        public int top() {
            if(stack.empty()){
                return -1;
            }
            return stack.peek();
        }

        public int getMin() {
            if(minStack.empty()){
                return -1;
            }
            return minStack.peek();
        }
    }

}
